package qjc.h_二叉树;

import com.二叉树.练习题.TreeNode;

public class h9_二叉搜索树中第K小元素 {
    /**
     * 核心思想：
     * - BST 的中序遍历（左 → 根 → 右）结果是严格递增的序列；
     * - 因此，中序遍历到第 k 个节点时，其值就是第 k 小的元素；
     * - 一旦找到第 k 个，可提前终止后续遍历，提高效率。
     *
     * @param root
     * @param k
     * @return
     */
    int k = 0;
    int res = 0;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (k == 0) {
            return;
        }
        if (--k == 0) {
            res = root.val;
            return;
        }
        dfs(root.right);
    }
}
